package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.计数DP;

import java.util.Scanner;

//未优化代码
class dp_278 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int num;
        int[][] dp = new int[N + 1][M + 1];
        /*
        dp[i][j]：表示所有从前i个数中选，总和为j的所有选法
        不选第i个数：
            dp[i][j] = dp[i - 1][j];
        选第i个数：
            dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - num] + 1);
        */
        //所有从前i个数中选，和为0的方案数都默认为1，即都不选也为一种方案
        for (int i = 0; i <= N; i++) dp[i][0] = 1;
        for (int i = 1; i <= N; i++) {
            num = in.nextInt();
            for (int j = 1; j <= M; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    //当前的方案数 = 选当前数的方案数 + 不选当前数的方案数
                    dp[i][j] = dp[i - 1][j - num] + dp[i - 1][j];
                }
            }
        }
        System.out.print(dp[N][M]);
    }
}
/*
优化后代码
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int num;
        int[] dp = new int[M + 1];
        //默认不选也是一种方案
        dp[0] = 1;
        for (int i = 1; i <= N; i++) {
            num = in.nextInt();
            for (int j = M; j >= num; j--) {
                dp[j] = dp[j - num] + dp[j];
            }
        }
        System.out.print(dp[M]);
    }
}

*/
